def helper(nums: list[int], exp: int):
    # 初始化桶
    bucket = [0] * 10

    # 元素入桶：统计 0~9 出现的次数
    for num in nums:
        bucket[(num // exp) % 10] += 1
    # 计算前缀和
    for i in range(1, 10):
        bucket[i] += bucket[i - 1]

    # 反向遍历原数组将元素，根据前缀和（排序位置）放入临时数组
    n = len(nums)
    tmp = [0] * n
    for i in range(n - 1, -1, -1):
        d = (nums[i] // exp) % 10
        tmp[bucket[d] - 1] = nums[i]  # 注意前缀和要减 1 才是索引！
        bucket[d] -= 1

    # 覆盖原数组
    for i in range(n):
        nums[i] = tmp[i]


def radix_sort(nums: list[int]):
    """基数排序"""
    max_num = max(nums)
    exp = 1
    while exp < max_num:  # 注意终止条件！
        helper(nums, exp)
        exp *= 10


if __name__ == "__main__":
    # 设输入数据为浮点数，范围为 [0, 1)
    nums = [105, 356, 428, 348, 818]
    radix_sort(nums)
    print("排序完成后 nums =", nums)
    # 排序完成后 nums = [0, 0, 0, 1, 1, 2, 2, 2, 4, 4]
